数据结构 Tree 红黑树

TODO: 本篇笔记年代久远，等学习到红黑树时再重新学习~

红黑树是什么？

红黑树(Red Black Tree) 是一种自平衡的二叉查找树。除了符合二叉查找树的基本特征外

它还制定了一些规则

1. 节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶子节点都是黑色的空节点（NIL节点）。
4. 每个红色节点的两个子节点都是黑色。（推导出一条路径上不能有两个连续的红色节点）
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

如下所示：

由上图可见，插入的节点都是红色的。因为要满足红黑树的这五条性质，如果我们插入的是黑色节点，那就违反了性质五，需要进行大规模调整，如果我们插入的是红色节点，那就只有在要插入节点的父节点也是红色的时候违反性质四或者是当插入的节点是根节点时，违反性质二，所以，我们把要插入的节点的颜色变成红色。

红黑树-插入

调整

当插入一个节点破坏规则时就需要进行调整

有两种调整的方法

• 变色
• 旋转
  • 左旋转
  • 右旋转

不需要做任何变色或者旋转的情况： 新插入的节点父节点是黑色，皆大欢喜。

需要做变色的情况：

1. 新插入的节点是根节点，根据rule2,颜色变成黑色，相当简单。
2. 如果它的父节点也是红色，违反了rule4，此时如果发现叔节点也是红色，那么将父与叔节点标记为黑色，祖节点为红色，然后把祖节点当作新插入的节点递归重复这一判断，直到根节点，将根节点颜色设置为黑色。

需要做变色与旋转的情况： 当叔节点是黑色，需要做旋转

左旋转 右旋转 就再去找资料吧

变色例子

例如向树中插入21的新节点时(注意！默认插入的节点必须是红色的)

由于父节点22是红色节点，因此这种情况打破了红黑树的规则4（每个红色节点的两个子节点都是黑色），必须进行调整，使之重新符合红黑树的规则。

为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。 1、需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色

2、但这样并不算完，因为凭空多出的黑色节点打破了 规则5 (从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点)，所以发生连锁反应，需要继续把节点25从黑色变成红色：

3、此时仍然没有结束，因为节点25和节点27又形成了两个连续的红色节点，需要继续把节点27从红色变成黑色：

插入的几种状况

参考这里

下面是可能遇到的插入的几种状况： 1、当插入的节点是根节点时，直接涂黑即可；

2、当要插入的节点的父节点是黑色的时候。

这个时候插入一个红色的节点并没有对这五个性质产生破坏。所以直接插入不用在进行调整操作。

3、如果要插入的节点的父节点是红色且父节点是祖父节点的 左支 的时候。

这个要分两种情况，一种是 叔叔节点为黑 的情况，一种是 叔叔节点为红 的情况。

当叔叔为黑时 也分为两种情况，

一种是要插入的节点是父节点的左支，另一种是要插入的节点是父亲的右支。

• 当要插入的节点是父节点的左支的情况：

  这个时候违反了性质四，我们就需要进行调整操作，使之符合性质四，我们可以通过对祖父节点进行右旋同时将祖父节点和父节点的颜色进行互换，这样就变成了：

  

  经过这样的调整可以符合性质四并且不对其他性质产生破坏。

• 当要插入的节点是父节点的右支的时候 我们可以先对父节点进行左旋，变成如下：

  如果我们把原先的父节点看做是新的要插入的节点，把原先要插入的节点看做是新的父节点，那就变成了当要插入的节点在父节点的左支的情况，对，是的，就是按照当要插入的节点在父节点的左支的情况进行旋转，旋转完之后变成如下：

---

4、如果要插入的节点的父节点是红色并且叔叔节点也为红色，如下： 当叔叔为红时

这个时候，只需将父亲节点和叔叔节点涂黑，将祖父节点涂红。

---

5、如果要插入的节点的父节点是红色且父节点是祖父节点的右支的时候； 这个时候的情况跟情况3所表述的情况是一个镜像，将情况3的左和右互换一下就可以了。

红黑树-删除

以后再研究吧 参考

B-Tree和B+Tree

参考

度的定义

节点的度：一个节点含有的子树的个数称为该节点的度；

树的度：一棵树中，最大的节点的度称为树的度；

叶节点或终端节点：度为零的节点；

非终端节点或分支节点：度不为零的节点；

B-Tree

为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]， key：为记录的键值，对于不同数据记录，key是互不相同的； data：为数据记录除key外的数据。 那么B-Tree是满足下列条件的数据结构：

• d为大于1的一个正整数，称为B-Tree的度。(一个节点含有的子树的个数称为该节点的度)
  
• h为一个正整数，称为B-Tree的高度。
  
• 每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d。
  
• 每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null 。
  
• 所有叶节点具有相同的深度，等于树高h。
  
• key和指针互相间隔，节点两端是指针。
  
• 一个节点中的key从左到右非递减排列。
  
• 所有节点组成树结构。
  
• 每个指针要么为null，要么指向另外一个节点。
  
• 如果某个指针在节点node最左边且不为null，则其指向节点的所有key小于 $v(key_1)$ ,其中 $v(key_1)$ 为node的第一个key的值。
  
• 如果某个指针在节点node最右边且不为null，则其指向节点的所有key大于 $v(key_m)$ ,其中 $v(key_m)$ 为node的最后一个key的值。
  
• 如果某个指针在节点node的左右相邻key分别是 $v(key_i)$ 和 $v(key_{i+1})$ 且不为null，则其指向节点的所有key小于 $v(key_{i+1})$ 且大于 $v(key_i)$ 。

总之有点红黑树的左边一定比右边小的内味了， 但是区别在于，这个实际上就是把一个list部分拆开(用指针连接)，使之更加自由 因为是指针连接，所以可以在每个节点之间插入更多的值

如图:在每个节点之间可以插入无数的节点，如果不存在则返回null

图是一个d=2的B-Tree示意图。

由于B-Tree的特性，在B-Tree中按key检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。

B+Tree

B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。

与B-Tree相比，B+Tree有以下不同点：

• 每个节点的指针上限为2d而不是2d+1。
• 内节点不存储data，只存储key；叶子节点不存储指针(数据都放叶子上)。

如图是一个简单的B+Tree示意。

由于并不是所有节点都具有相同的域，因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同，虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对每个节点申请同等大小的空间。

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。

Reference

参考-知乎:漫画：什么是红黑树？ 参考-知乎:红黑树的变色与旋转